package cn.xkai.exercise.a;

/**
 * @description: 最长回文子串
 * 自己的思路：中心扩散，奇偶回文串的查找，加入了多个判断来兼容奇偶回文串的边界判断，通用成一个底层方法subPalindrome
 * 借鉴的思路：中心扩散，奇偶回文串的长度查找，根据当前索引和奇偶判断回文串起始索引，根据回文串长度截取原始字符串
 * 心得：借鉴的思路奇偶回文串优先获取起始索引和长度，逻辑更明确、更清晰，也更简洁；自己的思路想着直接拿到回文串，然后比对串的长度做替换
 * @author: kaixiang
 * @date: 2022-06-23
 **/
public class Solution9 {
    public String longestPalindrome(String s) {
        StringBuilder longestPalindrome = new StringBuilder();
        longestPalindrome.append(s.charAt(0));
        // 奇数回文串
        for (int i = 1; i < s.length() - 1; i++) {
            subPalindrome(i - 1, i + 1, s, longestPalindrome);
        }
        // 偶数回文串
        for (int i = 0; i < s.length(); i++) {
            evenPalindrome(s, i, longestPalindrome);
        }
        return longestPalindrome.toString();
    }

    private void evenPalindrome(String s, int index, StringBuilder longestPalindrome) {
        if (index - 1 >= 0 && s.charAt(index) == s.charAt(index - 1)) {
            subPalindrome(index - 1, index, s, longestPalindrome);
        } else if (index + 1 < s.length() && s.charAt(index) == s.charAt(index + 1)) {
            subPalindrome(index, index + 1, s, longestPalindrome);
        }
    }

    private void subPalindrome(int left, int right, String s, StringBuilder longestPalindrome) {
        boolean skip = true;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left--;
            right++;
            skip = false;
        }
        if (!skip) {
            String palindrome;
            if (left < 0) {
                palindrome = s.substring(0, right);
            } else if (right >= s.length()) {
                palindrome = s.substring(left + 1);
            } else {
                palindrome = s.substring(left + 1, right);
            }
            if (palindrome.length() > longestPalindrome.length()) {
                longestPalindrome.delete(0, longestPalindrome.length()).append(palindrome);
            }
        }
    }


    public String longestPalindromeRefer(String s) {
        if (s == null || s.length() < 2) return s;
        int resIdx = 0, resLen = 1;
        for (int idx = 0; idx < s.length() - 1; idx++) {
            //奇数最长回文长度
            int len1 = longestLen(s, idx, idx);
            //偶数最长回文长度
            int len2 = longestLen(s, idx, idx + 1);
            if (len1 > resLen) {
                resLen = len1;
                resIdx = idx - resLen / 2;
            }
            if (len2 > resLen) {
                resLen = len2;
                resIdx = idx - (resLen / 2 - 1);
            }
        }
        return s.substring(resIdx, resIdx + resLen);
    }

    private int longestLen(String s, int left, int right) {
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) break;
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static void main(String[] args) {
        String s = "babab";
        Solution9 solution9 = new Solution9();
        System.out.println(solution9.longestPalindrome(s));
    }
}
